package srm514;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class MagicalGirlLevelTwoDivTwo {
    private final String YES = "YES", NO = "NO";
    private int base;

    public String isReachable(int[] jumpTypes, int x, int y) {
        if (x == 0 && y == 0) {
            return YES;
        }
        base = (int) ((System.currentTimeMillis() + 313717) % 1000000 + 200000);
        while (!BigInteger.valueOf(base).isProbablePrime(100)) base++;

        Set<Node> visited = new HashSet<Node>();
        Queue<Node> q = new LinkedList<Node>();
        Node node = new Node(0, 0);
        visited.add(node);
        q.add(node);
        int signX[] = new int[]{1, 1, -1, -1};
        int signY[] = new int[]{1, -1, 1, -1};

        int jLen = jumpTypes.length;
        while (q.size() > 0) {
            node = q.poll();
            int xd = node.x, yd = node.y, nx, ny;
            for (int i = 0; i < jLen; i++) {
                int n[] = {jumpTypes[i], 1};
                for (int j = 0; j < 2; j++) {
                    int a = n[j], b = n[1 - j];
                    for (int k = 0; k < 4; k++) {
                        nx = signX[k] * a;
                        ny = signY[k] * b;
                        Node t = new Node(xd + nx, yd + ny);
                        if (visited.contains(t)) continue;
                        if (x == t.x && y == t.y)
                            return YES;
                        t.level = node.level + 1;
                        if (t.level > 100 || Math.abs(t.x - x) > 180 || Math.abs(t.y - y) > 180) {
                            visited.add(t);
                            continue;
                        }
                        q.add(t);
                        visited.add(t);
                    }
                }
            }
        }
        return NO;
    }

    private class Node {
        int x, y, level = 0;

        Node(int a, int b) {
            x = a;
            y = b;
        }

        Node() {

        }

        @Override
        public String toString() {
            return x + "," + y;
        }

        @Override
        public boolean equals(Object obj) {
            Node other = (Node) obj;
            return x == other.x && y == other.y;
        }

        @Override
        public int hashCode() {
            return x * base + y;
        }
    }

    // BEGIN KAWIGIEDIT TESTING
    // Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
    private static boolean KawigiEdit_RunTest(int testNum, int[] p0, int p1, int p2, boolean hasAnswer, String p3) {
        System.out.print("Test " + testNum + ": [" + "{");
        for (int i = 0; p0.length > i; ++i) {
            if (i > 0) {
                System.out.print(",");
            }
            System.out.print(p0[i]);
        }
        System.out.print("}" + "," + p1 + "," + p2);
        System.out.println("]");
        MagicalGirlLevelTwoDivTwo obj;
        String answer;
        obj = new MagicalGirlLevelTwoDivTwo();
        long startTime = System.currentTimeMillis();
        answer = obj.isReachable(p0, p1, p2);
        long endTime = System.currentTimeMillis();
        boolean res;
        res = true;
        System.out.println("Time: " + (endTime - startTime) / 1000.0 + " seconds");
        if (hasAnswer) {
            System.out.println("Desired answer:");
            System.out.println("\t" + "\"" + p3 + "\"");
        }
        System.out.println("Your answer:");
        System.out.println("\t" + "\"" + answer + "\"");
        if (hasAnswer) {
            res = answer.equals(p3);
        }
        if (!res) {
            System.out.println("DOESN'T MATCH!!!!");
        } else if ((endTime - startTime) / 1000.0 >= 2) {
            System.out.println("FAIL the timeout");
            res = false;
        } else if (hasAnswer) {
            System.out.println("Match :-)");
        } else {
            System.out.println("OK, but is it right?");
        }
        System.out.println("");
        return res;
    }

    public static void main(String[] args) {
        boolean all_right;
        all_right = true;

        int[] p0;
        int p1;
        int p2;
        String p3;

        // ----- test 0 -----
        p0 = new int[]{2};
        p1 = 5;
        p2 = 4;
        p3 = "YES";
        all_right = KawigiEdit_RunTest(0, p0, p1, p2, true, p3) && all_right;
        // ------------------

        // ----- test 1 -----
        p0 = new int[]{3};
        p1 = 5;
        p2 = 4;
        p3 = "NO";
        all_right = KawigiEdit_RunTest(1, p0, p1, p2, true, p3) && all_right;
        // ------------------

        // ----- test 2 -----
        p0 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        p1 = -30;
        p2 = 27;
        p3 = "YES";
        all_right = KawigiEdit_RunTest(2, p0, p1, p2, true, p3) && all_right;
        // ------------------

        // ----- test 3 -----
        p0 = new int[]{29};
        p1 = 29;
        p2 = 0;
        p3 = "NO";
        all_right = KawigiEdit_RunTest(3, p0, p1, p2, true, p3) && all_right;
        // ------------------

        p0 = new int[]{1, 29};
        p1 = 30;
        p2 = 30;
        p3 = "YES";
        all_right = KawigiEdit_RunTest(3, p0, p1, p2, true, p3) && all_right;
        // ------------------

        if (all_right) {
            System.out.println("You're a stud (at least on the example cases)!");
        } else {
            System.out.println("Some of the test cases had errors.");
        }
    }
    // END KAWIGIEDIT TESTING
}
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
